package com.origin.niuke.tree;

import general_class.TreeNode;

/**
 * NC58 找到搜索二叉树中两个错误的节点
 * 算法：中序遍历
 * 二叉搜索树的两个节点位置调换后, 第一个错误的节点肯定比它后一个位置的节点大
 * 第二个错误的节点肯定比它前一个位置的节点小
 *
 * @author yezh
 * @version 1.0
 * @date 2022/11/3 21:20
 */
public class NC58 {

    int pre, idx;
    int[] ans;

    public int[] findError(TreeNode root) {
        // write code here
        pre = 0;
        idx = 1;
        ans = new int[2];
        dfs(root);
        return ans;
    }

    void dfs(TreeNode node) {
        if (node == null || pre == -1) return;
        dfs(node.left);
        if (node.val < pre) {
            if (idx == 1) {
                // 第一次找到当前值小于上一个值的, 表示 pre 是从后面位置换到前面的
                ans[idx] = pre;
                // 当相连的两个节点调换位置时
                ans[idx - 1] = node.val;
            } else ans[idx] = node.val; // 第二次找到当前值小于上一个值的, 表示当前值是从前面位置换到后面的
            --idx;
            if (idx == -1) pre = -1;
        }
        pre = node.val;
        dfs(node.right);
    }

}
